import java.util.*;

/**
 * 127. 单词接龙
 * https://leetcode.cn/problems/word-ladder/description/
 */
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hash = new HashSet<>();
        Set<String> vist = new HashSet<>();

        //把wordList全部存进hash表里
        for(String word : wordList) {
            hash.add(word);
        }

        if(beginWord.equals(endWord)) return 2;
        if(!hash.contains(endWord)) return 0;

        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vist.add(beginWord);

        int step = 0;

        while(!q.isEmpty()) {
            step++;
            int sz = q.size();
            while(sz-- != 0) {
                String t = q.poll();
                for(int i = 0; i < t.length(); i++) {
                    char[] tmp = t.toCharArray();
                    for(char ch = 'a'; ch <= 'z'; ch++) {
                        tmp[i] = ch;
                        String s = new String(tmp);
                        if(s.equals(endWord)) return step+1;
                        if(!vist.contains(s) && hash.contains(s)) {
                            q.add(s);
                            vist.add(s);
                        }
                    }
                }
            }
        }

        return 0;
    }
}